package com.leecode.medium.get2sum001;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * @author ymsxyz
 * @version 1.0
 * @desc 核心:1.无序链表求和,转换:(1)null判断;(2)赋值到新容器List;2.递归完成ListNode和ArrayList数据转换
 * @date 2021/1/30 1:49
 */
public class Solution {
    //用于递归获取ListNode的数据
    private ArrayList<Integer> list = new ArrayList<>();
    private int i = 0;//遍历list 赋值
    private ListNode reListNode = null;//用来保存递归的数据

    /**
     * @return void
     * @desc 测试类
     * @author ymsxyz
     * @date 2021/1/30 1:47
     */
    @Test
    public void test1() {
        /*
            测试参数:
            [0][0]=>[0];
            [3,9][8,0]=>[1,0,1];
            [2,4,9][5,6,4,9]=>[7,0,4,0,1];
            [9,9,9][9,9,9,9,9]=>[8,9,9,0,0,1]

         */
        ListNode listNode = addTwoNumbers(new ListNode(0), new ListNode(0));
        //初始化变量
        i = 0;
        reListNode = null;
        ListNode listNode1 = addTwoNumbers(
                new ListNode(3, new ListNode(9)),
                new ListNode(8, new ListNode(0)));
        i = 0;
        reListNode = null;
        ListNode listNode2 = addTwoNumbers(
                new ListNode(2, new ListNode(4, new ListNode(9))),
                new ListNode(5, new ListNode(6, new ListNode(4, new ListNode(9)))));
        i = 0;
        reListNode = null;
        ListNode listNode3 = addTwoNumbers(
                new ListNode(9, new ListNode(9, new ListNode(9))),
                new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9))))));
        i = 0;
        reListNode = null;
    }

    /**
     * @param l1
     * @param l2
     * @return com.leecode.medium.get2sum.ListNode
     * @desc 两无索引链表求和问题
     * @author ymsxyz
     * @date 2021/1/30 1:44
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        /*
            分析:
                时间复杂度T(n)
                需要:从最后一个节点开始计算,链表无法实现,定义3个ArrayList集合存储数据,再实现功能
                关键:ListNode数据储存到ArrayList和取出(递归)
        */
        ListNode l3 = new ListNode();
        //定义三个容器装链表元素
        ArrayList<Integer> arr1 = new ArrayList<>();
        ArrayList<Integer> arr2 = new ArrayList<>();
        ArrayList<Integer> arr3 = new ArrayList<>();

        //深克隆

        arr1 = new ArrayList<>(listNodeToList(l1));
        //清空list
        list.clear();
        arr2 = new ArrayList<>(listNodeToList(l2));
        list.clear();

        //判断arr1和arr2长度
        int maxlenth = arr1.size() > arr2.size() ? arr1.size() : arr2.size();
        int minlenth = arr1.size() <= arr2.size() ? arr1.size() : arr2.size();
        //定义arrMax指针指向长度大的集合地址
        ArrayList<Integer> maxArr = arr1.size() > arr2.size() ? arr1 : arr2;
        //
        int i1 = 0;//l1中元素值
        int i2 = 0;//l2中元素值
        int i3 = 0;//l3中元素值
        int v = 0;//两数和是否大于10,大于则v赋值1

        //计算1:开始求和计算,直到短数组元素结束
        for (int i = 0; i < minlenth; i++) {
            i1 = arr1.get(i);
            i2 = arr2.get(i);
            i3 = i1 + i2;
            //判断两数(+v)之和是否大于等于10
            if (i3 + v >= 10) {
                i3 = i3 - 10 + v;
                arr3.add(i3);
                v = 1;
            } else {
                i3 = i3 + v;
                arr3.add(i3);
                v = 0;
            }
        }
        //注意:v的值依然有效
        //计算2:集合长度大的继续给arr3元素赋值,注意:尾部可能为9+1=10,进一位
        for (int i = 0; i <= maxlenth - minlenth; i++) {//如:8-4 0-4多一位

            //最后一次,判断v是否为1,是则arr3再加一位,否则结束循环
            if (i == maxlenth - minlenth) {
                if (v == 1) {
                    arr3.add(v);
                    break;
                } else {
                    break;
                }
            }
            //以短集合长度为索引开始取值
            i1 = maxArr.get(minlenth + i);
            i3 = i1 + v;
            if (i3 >= 10) {//注意:这里也需要判断,如:99 v=1
                i3 -= 10;
                arr3.add(i3);
                v = 1;
            } else {
                arr3.add(i3);
                v = 0;
            }

        }

        //怎么将数据装入ListNode
        //测试arr3是否正确
        //System.out.print(arr3.get(i) + "\t");
        Collections.reverse(arr3);
        l3 = listToListNode(arr3);
        return l3;
    }

    /**
     * @return java.util.List<java.lang.Integer>
     * @desc 无索引链表数据储存到有索引的链表中
     * @author ymsxyz
     * @date 2021/1/29 22:21
     */
    private List<Integer> listNodeToList(ListNode listNode) {
        list.add(listNode.val);//listNode不为null,至少有一个值
        //递归 若还有值
        if (listNode.next != null) {
            listNodeToList(listNode.next);
        }
        return list;
    }

    /**
     * @return com.leecode.medium.get2sum.ListNode
     * @desc 集合中元素储存到ListNode中, 递归 通过成员变量i判断是否取值完毕
     * @author ymsxyz
     * @date 2021/1/29 22:23
     */
    private ListNode listToListNode(ArrayList<Integer> list) {

        //list还有值,则循环 给next赋值
        while (list.size() > i) {
            reListNode = new ListNode(list.get(i), reListNode);
            i++;
            listToListNode(list);
        }
        return reListNode;//list赋值完毕 只有最后一次执行到
    }

}
